package com.algrithom.tree.bst;

import java.util.Objects;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 剑指 Offer II 053. 二叉搜索树中的中序后继
 * 
 * @author think
 */
public class Solution2 {
    
    private TreeNode<Integer> ans = new TreeNode<>();
    
    private boolean isp = false;
    
    public static void main(String[] args){
        Integer[] list = new Integer[]{5,3,6,2,4,null,null,1};
        TreeNode<Integer> root = TreeOperUtil.createTree(list,0);
        Solution2 solution2 = new Solution2();
        // solution2.inorderSuccessor(root, 6);
        // System.out.println(solution2.ans.getValue());
        TreeNode<Integer> result = solution2.inorderSuccessor2(root,6);
        System.out.println(Objects.isNull(result) ? null : result.getValue());
    }
    
    private TreeNode<Integer> inorderSuccessor(TreeNode<Integer> root,int p){
        dfs(root,p);
        return ans;
    }
    
    private void dfs(TreeNode<Integer> root,int val){
        if (Objects.isNull(root)) {
            return;
        }
        dfs(root.getLeftChild(),val);
        if (root.getValue() == val) {
            isp = true;
        }
        if (isp && Objects.isNull(ans)) {
            ans = root;
            return;
        }
        dfs(root.getRightChild(),val);
    }
    
    private TreeNode<Integer> inorderSuccessor2(TreeNode<Integer> root,int p){
        TreeNode<Integer> cur = root;
        TreeNode<Integer> result = null;
        while (Objects.nonNull(cur)) {
            if (cur.getValue() > p) {
                result = cur;
                if (Objects.nonNull(cur.getLeftChild())) {
                    cur = cur.getLeftChild();
                } else {
                    cur = null;
                }
            } else {
                if (Objects.nonNull(cur.getRightChild())) {
                    cur = cur.getRightChild();
                } else {
                    cur = null;
                }
            }
        }
        return result;
    }
}